package com.leetcode.weekly.contest.no235th;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2021-04-04 11:42
 */
public class A04_序列中不同最大公约数的数目 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] nums = {6, 10, 3};
    int diffNum = solution.countDifferentSubsequenceGCDs(nums);
    System.out.println(diffNum);
  }


  static
  class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {

      Set<Integer> result = new HashSet<>();
      Deque<Node> queue = new ArrayDeque<>();
      for (int i = 0; i < nums.length; ++i) {
        queue.add(new Node(nums[i], i + 1));
        result.add(nums[i]);
      }

      while (!queue.isEmpty()) {
        Node node = queue.poll();
        if (node.gcd == 1 || node.nextIndex >= nums.length) {
          continue;
        }
        queue.add(new Node(node.gcd, node.nextIndex + 1));

        int nextNum = nums[node.nextIndex];
        int gcd = gcd(node.gcd, nextNum);
        result.add(gcd);
        queue.add(new Node(gcd, node.nextIndex + 1));
      }

      return result.size();
    }

    private int gcd(int a, int b) {
      while (a % b != 0) {
        int tmp = a % b;
        a = b;
        b = tmp;
      }
      return b;
    }

    private static class Node {

      int gcd;

      int nextIndex;

      public Node(int gcd, int nextIndex) {
        this.gcd = gcd;
        this.nextIndex = nextIndex;
      }
    }
  }

}
